#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
'''
给定一个数组，求如果排序之后，相邻两数的最大差值，要求时 间复杂度O(N)，且要求不能用非基于比较的排序。
'''

# 巧妙得函数，求取某个数所在得桶
def bucket(num: int, length: int, imin: int, imax: int)->int:
    return (num - imin) * length // (imax - imin)

def max_gap(arr: list) -> int:
    length = len(arr)
    if not arr or length < 2: return 0

    imin = min(arr)
    imax = max(arr)

    if imin == imax : return 0

    hasnum = [False] * (length + 1) # 每个桶是否有数据
    imins = [imax] * (length + 1) # 每个桶的最小值
    imaxs = [imin] * (length + 1) # 每个桶的最大值
    bid = 0 # 求得得当前数所在桶的下标
    for i in range(length):
        bid = bucket(arr[i], length, imin, imax)
        if hasnum[bid]:  # 如果该桶已经有数
            imins[bid] = min(imins[bid], arr[i])
            imaxs[bid] = max(imaxs[bid], arr[i])
        else:
            imins[bid] = arr[i]
            imaxs[bid] = arr[i]
            hasnum[bid] = True
    res = 0 # 返回结果
    lastmax = imaxs[0]  # 上一个相邻得非空桶得最大值
    for i in range(1, length + 1):  # 这个地方容易出错，因为是length+1 个桶， 所以要注意
        if hasnum[i]:
            res = max(res, (imins[i] - lastmax))
            lastmax = imaxs[i]
    return res

def compare(arr: list) -> int:
    length = len(arr)
    if not arr or length < 2: return 0
    arr.sort()
    import sys
    gap = -sys.maxsize - 1
    for i in range(1, length):
        gap = max(gap, arr[i] - arr[i-1])
    return gap



import random

def generate_random_array(max_size: int, max_value: int) -> list :
    length = random.randint(1, max_size )  #random.randint结果包括右边界
    arr = []
    for i in range(length):
        arr.append(random.randint(1, max_value) - random.randint(1, max_value))
    return arr

def copy_array(arr: list) -> list:
    if len(arr) == 0 : return None
# list2 = list1.copy()
    return arr[:]
def print_array(arr: list) :
    if not arr: return
    print(arr)

def main():
    test_time = 500
    max_size = 100
    max_value = 100
    succeed = True
    for i in range(test_time):
        arr1 = generate_random_array(max_size, max_value)
        arr2 = copy_array(arr1)
        arr3 = copy_array(arr1)
        if compare(arr2) != max_gap(arr1) :
            succeed = False
            print(f'compare(arr2):{compare(arr2)}')
            print(f'max_gap(arr1):{max_gap(arr1)}')
            break

    print('Nice!' if succeed else 'Fucking fucked!')
    if succeed is False:
        print("compare\n")
        print_array(arr2)
        print("max_gap\n")
        print_array(arr1)
        print("raw\n")
        print_array(arr3)

if __name__ == "__main__":
     main()